package org.example.entity;

import java.util.Hashtable;

/**
 * 146. LRU 缓存
 */
public class LRUCache {
    private int capacity;
    private DLinkedNode head, tail;
    private Hashtable<Integer, DLinkedNode> cache=new Hashtable<>();
    private int size;

    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;

        public DLinkedNode() {}

        public DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }


    /**
     * 添加节点到链表头部
     * @param node 节点
     */
    private void addNode(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    /**
     * 删除链表中的节点
     * @param node 节点
     */
    private void removeNode(DLinkedNode node) {
        DLinkedNode prev = node.prev;
        DLinkedNode next = node.next;
        prev.next = next;
        next.prev = prev;
    }

    /**
     * 移动节点到链表头部
     * @param node 节点
     */
    private void moveToHead(DLinkedNode node) {
        this.removeNode(node);
        this.addNode(node);
    }

    /**
     * 删除链表尾部节点并返回该节点
     * @return 节点
     */
    private DLinkedNode popTail() {
        DLinkedNode res = tail.prev;
        this.removeNode(res);
        return res;
    }

    /**
     * 构造函数
     * @param capacity 容量
     */
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    /**
     * 获取缓存中的值
     * @param key 键
     * @return 值
     */
    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        this.moveToHead(node);
        return node.value;
    }

    /**
     * 添加缓存
     * @param key 键
     * @param value 值
     */
    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;
            this.cache.put(key, newNode);
            this.addNode(newNode);
            this.size++;
            if (this.size > this.capacity) {
                DLinkedNode tail = this.popTail();
                this.cache.remove(tail.key);
                this.size--;
            }
        }else{
            node.value = value;
            this.moveToHead(node);
        }
    }
}